//
// Created by 朱语 on 2022/8/4.
//

#include "graph.h"
#include "iostream"
#include <queue>
#include <stack>
using namespace std;

int belongTo(vector<int>& parent, int vertex, int end);

graph::graph() {
    cout<<"create graph"<<endl;
}

graph::graph(int side, int init_side) {
    cout<<"create graph"<<endl;
    _graph.resize(side, vector<int>(side, init_side));
    init_weight = init_side;
    size = side;
}

graph::~graph() {
    cout<<"kill graph"<<endl;
}

void graph::build(vector<vector<int> > &pair) {
    for(auto row : pair){
        if(row.size() != 2 && row.size() != 3){
            cerr<<"build failed: data not compete"<<endl;
            exit(0);
        }
        if(row[0] >= size || row[1] >= size ){
            cerr<<"build failed: index out of bond"<<endl;
        }
        if(row.size() == 2){//默认权重为1，相当于无权图
            _graph[row[0]][row[1]] = 1;
            _graph[row[1]][row[0]] = 1;
        }else{
            _graph[row[0]][row[1]] = row[2];
            _graph[row[1]][row[0]] = row[2];
        }
    }
}

bool graph::connected() {
    vector<bool> visited(size, false);
    queue<int> q;
    //每个节点都联通，则0一定也联通，从0开始
    q.push(0);
    visited[0] = true;

    while(!q.empty()){
        int idx= q.front();
        q.pop();
        for(int j = idx+1; j < size ; j++){
            if(_graph[idx][j] != 0){
                visited[j] = true;
                q.push(j);
            }
        }
    }

    for(auto it : visited)
        if(it == false){
            return false;
        }

    return true;

}

//深度优先搜索
//以0为起点位置
void graph::DFS(int start) {
    vector<bool> visited(size, false);
    cout<<"DFS-recursion"<<endl;
    dfs(visited, start);
    cout<<endl;
    cout<<"DFS-iterate"<<endl;

    for(auto item : visited)
        item = false;

    dfs_iter(visited, start);
    cout<<endl;
}

//广度优先搜索
//以0为起点位置
void graph::BFS(int start) {
    cout<<"BFS-iterate"<<endl;
    vector<bool> visited(size, false);
    bfs_iter(visited, start);
    cout<<endl;
}

/* 要求：
 * 图不连通为0，联通为1
 * 思路：
 * 因为每一条边的权重均为1，所以直接按照BFS的思路就可以判断谁远谁近
 */
void graph::UnWeighted(int start) {
    vector<int> dist(size, -1);//所有距离初始化为-1
    vector<int> parent(size, -1);
    queue<int> q;

    //将起点初始化
    dist[start] = 0;
    //parent[start] = -1;

    //起点加入队列
    q.push(start);

    while(!q.empty()){
        //拿到队列头
        int vertex = q.front();
        q.pop();
        //对vertex的每一个邻接点
        for(int i = 0 ; i < size ; i++){
            //找到vertex的邻接点
            if( i != vertex && _graph[vertex][i] != init_weight){
                //路径未计算出,计算路径
                if(dist[i] == -1){
                    //在vertex的基础上+1
                    dist[i] = dist[vertex] + 1;
                    parent[i] = vertex;
                    q.push(i);
                }
            }
        }
    }

    //输出结果
    cout<<"unweighted_graph path"<<endl;
    path_print(dist, parent, start, -1);

}

/*
 * 要求：
 * 有权图，权重不可为负
 * 思路：
 * 额外开辟一个collected数组标记是否已经被收录到生成树中
 * 功能类似于visited，但不完全相同
 */
void graph::Dijkstra(int start) {
    vector<int> dist(size, INT_MAX);//所有距离初始化为最大值
    vector<int> parent(size, -1);
    vector<bool> collected(size, false);

    //处理第一个节点
    dist[start] = 0;
    parent[start] = -1;
    collected[start] = true;

    //算法主体
    while(true){
        //检查是否全部收录
        int i = 0;
        for(; i < size ; i++){
            if(!collected[i])
                break;
        }
        if(i == size)
            break;

        //修改当前未收录的节点的距离值
        for(int vertex = 0 ; vertex < size ; vertex++){
            if(!collected[i]){
                for(int j = 0 ; j < size ; j++){
                    if(j != vertex && _graph[vertex][j] != init_weight && collected[j]) {
                        if(dist[vertex] > dist[j] + _graph[vertex][j]){
                            parent[vertex] = j;
                            dist[vertex] = dist[j] + _graph[vertex][j];
                        }
                    }
                }
            }
        }

        //找出距离值最小的未被收录的节点并收录
        int idx;
        int min_dist = INT_MAX;
        for( i = 0 ; i < size ; i++){
            if(!collected[i] && dist[i] < min_dist){
                idx = i;
                min_dist = dist[i];
            }
        }

        collected[idx] = true;
    }

    //输出
    cout<<"weighted_graph path --Dijkstra"<<endl;
    path_print(dist, parent, start, -1);
}

/*
 * 要求：
 * 有权图，权重不为负
 * 可以求出任意两点之间的最短距离，即所有点都可以是起点
 * 思路：
 * 三重循环
 */
void graph::Floyd() {
    //初始化
    vector<vector<int> > dist(_graph);
    vector<vector<int> > path(size, vector<int>(size, -1));

    for(int i = 0 ; i < size ; i++){
        dist[i][i] = 0;
        for(int j = 0 ; j < size ; j++)
            path[i][j] = i;
        path[i][i] = -1;
    }

    //算法
    for(int mid = 0 ; mid < size ; mid++){
        for(int start = 0 ; start < size ; start++){
            for(int end = 0 ; end < size ; end++){
                if(dist[start][mid] + dist[mid][end] < dist[start][end]){
                    dist[start][end] = dist[start][mid] + dist[mid][end];
                    path[start][end] = mid;
                }
            }
        }
    }

    //输出
    cout<<"weighted_graph --Floyd"<<endl;
    for(int i = 0 ; i < size ; i++){
        cout<<"start from: "<<i<<endl;
        path_print(dist[i], path[i], i, -1);
    }
//    for(auto it : dist[0])
//        cout<<it<<" ";
//    cout<<endl;
//    for(auto it : path[0])
//        cout<<it<<" ";
//    cout<<endl;


}

/*
 * Prim
 * 要求：
 * 有权图，联通
 * 特点：
 * 最小生成树
 * 总路径和最短，但每一条路不一定最短路径
 * 思路：
 * BFS
 */
void graph::Prim(int start) {
    //dist和collect其实只需要保留一个
    vector<int> dist(size, INT_MAX);
    vector<int> parent(size, -1);
    //vector<bool> collected(size, false);
    //初始化，从任意点开始结果一样，假定从0开始
    dist[start] = 0;
    int totaldist = 0;
    //collected[start] = true;

    //开始BFS
    while(true){
        //找到与树相连且不成环的最小边
        //使用最小堆和并查集会更快，方便起见使用了三重循环
        int min = INT_MAX;
        int vertex = -1;

        for(int i = 0 ; i < size ; i++){
            if(/*collected[i]*/ dist[i] == 0){
                for(int j = 0 ; j < size ; j++){
                    //没有收集，说明不成环
                    if(/*!collected[j]*/ dist[j] != 0 && _graph[i][j] != init_weight && _graph[i][j] < min){
                        min = _graph[i][j];
                        vertex = j;
                        parent[vertex] = i;//每次都更新parent，但只要不收录就无效
                    }
                }
            }
        }
        if(vertex == -1)
            break;
        else{
            //collected[vertex] = true;
            dist[vertex] = 0;
            totaldist += min;
        }
    }

    //输出结果
//    for(auto it : collected){
//        if(it == false){
//            cerr<<"非联通图"<<endl;
//            exit(0);
//        }
//    }
    for(auto it : dist){
        if(it != 0){
            cerr<<"graph not connected"<<endl;
            exit(0);
        }
    }

    cout<<"minimum spanning tree --Prim"<<endl;
    path_print(dist, parent, start, -1);
    cout<<"total distance is: "<<totaldist<<endl;

}

/*
 * Kruskal
 * 特点：
 * 树聚合成森林
 */
void graph::Kruskal() {
    vector<vector<int> > side(_graph);
    vector<int> dist(size, INT_MAX);
    vector<int> parent(size, -1);
    int totaldist = 0;
    int count = 0;

    //查找最小边，如果不成环则收录
    //最好使用最小堆和并查集
    while(true){
        int vertex1 = -1, vertex2 = -1;
        int min = INT_MAX;
        for(int i = 0 ; i < size ; i++){
            for(int j = 0 ; j < size ; j++){
                if( side[i][j] != init_weight && side[i][j] < min){
                    min = _graph[i][j];
                    vertex1 = i;
                    vertex2 = j;
                }

            }
        }

        if(vertex1 == -1 && vertex2 == -1)
            break;
        if(count == size -1)
            break;

        else{
            //如果有一个节点没有被收录到任何一棵树中，则收录
            //如果都被收录则考虑合并两棵树
            if(dist[vertex1] != 0 && dist[vertex2] != 0){
                dist[vertex1] = 0;
                dist[vertex2] = 0;
                parent[vertex2] = vertex1;
                totaldist += side[vertex1][vertex2];
                count++;
            }
            else if(dist[vertex1] != 0){
                dist[vertex1] = 0;
                parent[vertex1] = vertex2;
                totaldist += side[vertex1][vertex2];
                count++;
            }
            else if(dist[vertex2] != 0){
                dist[vertex2] = 0;
                parent[vertex2] = vertex1;
                totaldist += side[vertex1][vertex2];
                count++;
            }
            else{
                if(belongTo(parent, vertex1, -1) != belongTo(parent, vertex2, -1)){
                    totaldist += side[vertex1][vertex2];
                    count++;
                }
            }
            side[vertex1][vertex2] = init_weight;
        }

    }
    for(auto it : dist){
        if(it != 0){
            cerr<<"graph not connected"<<endl;
            exit(-1);
        }
    }
    cout<<"minimum spanning tree --Kruskal"<<endl;
    cout<<"total distance is: "<<totaldist<<endl;

}



/*------private------*/
void graph::dfs(vector<bool> & visited, int vertex) {
    if(!visited[vertex]){

        visited[vertex] = true;
        cout<<vertex<<" ";

        for(int i = 0; i < size ; i++){
            if(i != vertex && _graph[vertex][i] != init_weight){
                dfs(visited, i);
            }
        }

    }
}


void graph::dfs_iter(vector<bool> &visited, int start) {
    stack<int> s;
    s.push(start);

    while(!s.empty()){
        int vertex = s.top();

        if(!visited[vertex]){

            visited[vertex] = true;
            cout<<vertex<<" ";

            for(int i = size-1; i >= 0 ; i--){
                if(i != vertex && _graph[vertex][i] != init_weight ){
                    s.push(i);
                }
            }
        }
        else
            s.pop();
    }
}

void graph::bfs_iter(vector<bool> &visited, int start) {
    queue<int> q;
    q.push(start);

    //因为BFS没有回溯，不需要保留元素在栈底，而是使用队列
    //所以访问完可以直接pop
    /*
    while(!q.empty()){
        int vertex = q.front();
        if(!visited[vertex]){
            cout<<vertex<<" ";
            visited[vertex] = true;
            for(int i = 0 ; i < size ; i++){
                if(i != vertex && _graph[vertex][i] != init_weight){
                    q.push(i);
                }
            }
        }else{
            q.pop();
        }
    }
    */

    while(!q.empty()){
        int vertex = q.front();
        q.pop();//直接pop
        if(!visited[vertex]){
            cout<<vertex<<" ";
            visited[vertex] = true;
            for(int i = 0 ; i < size ; i++){
                if(i != vertex && _graph[vertex][i] != init_weight){
                    q.push(i);
                }
            }
        }
    }
}

void graph::path_print(vector<int> & dist, vector<int> & parent,int start, int end) {
    stack<int> path;
    for(int i = 0 ; i < size ; i++) {
        cout << i << " dist: " << dist[i] << " path: ";
        int j = i;
        while (j != end) {
            path.push(j);
            j = parent[j];
        }
        while (!path.empty()) {
            cout << (path.top() == start ? "" : "->") << path.top();
            path.pop();
        }
        cout << endl;
    }
}

/*--------other-------*/
int belongTo(vector<int>& parent, int vertex, int end){
    while(parent[vertex] != end)
        vertex = parent[vertex];
    return vertex;
}

